//
// Created by Senhai Xu on 2025/3/7.
// BM7 链表中环的入口结点
#include <unordered_set>
struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
  ListNode* EntryNodeOfLoop2(ListNode* pHead) {
    std::unordered_set<ListNode*> set;
    while (pHead) {
      if (set.find(pHead) != set.end()) {
        return pHead;
      }
      set.insert(pHead);
      pHead = pHead->next;
    }
    return nullptr;
  }
//  快慢指针
  ListNode* EntryNodeOfLoop(ListNode* pHead) {
//    找到慢指针所指向的节点
      ListNode* slow = hasCycle(pHead);
//      快指针回到头结点
      ListNode* fast = pHead;
      while(slow &&slow!=fast) {
        slow = slow->next;
        fast = fast->next;
      }
      
      return slow;
  }
//  快慢指针辅助函数
  ListNode* hasCycle(ListNode* pHead) {
    if(!pHead || !pHead->next) {
      return nullptr;
    }
    ListNode* slow = pHead;
    ListNode* fast = pHead;
    while(fast!=nullptr && fast->next!=nullptr){
      slow = slow->next;
      fast = fast->next->next;
      if(slow == fast) {
        return slow;
      }
    }
    return  nullptr;
  }
};